#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
int number[100000000];
int number2[100000000];
void  mergeSort(int *array,int length);
int __cmp(int *a,int *b)
{
  return *a-*b;
}
int main(int argc, char *argv[])
{
  int i=0;
  int length = 100000000;
  clock_t start,end;
     
  srand(5);
  for(i=0;i<length;i++)
    {
      number[i]=(int)rand();
      number2[i]=number[i];
    }
  
  start = clock();
  mergeSort(number,length);
  end = clock();
  printf ("%f\n",(double)end-start);

  start = clock();
  qsort(number2,length,sizeof(int),__cmp);
  end = clock();
  printf ("%f\n",(double)end-start);
  
  return 0;
}
void merge(int source[],int output[],int length,int start,int interval);
void mergeSort(int *array,int length)
{
  int *source,*buffer,*temp,*tofree;
  source = array;
  buffer = calloc(sizeof(int),length);
  int i=1;
  while(1)
    {
      int j=0;
      //done
      if(length/i==0)
	{
	  // make sure array buffer is sorted
	  if(tofree==buffer)
	    memcpy(source,buffer,length*sizeof(int));
	  return;
	}
      while(j*i*2<length)
	{
	  merge(source,buffer,length,j*i*2,i);
	  j++;
	}
      i*=2;
      temp = buffer;
      buffer =source;
      source = temp;
    }
}
void merge(int source[],int output[],int length,int start,int interval)
{  
  int pfirst,psecond,pout;
  int psecondMax=0;
  int n = 0;
  
  //if it's last group and length is not 2^n
  if(start+interval>=length)
    {
      return;
    }
  if(start+interval*2>=length)
    {
      psecondMax=length-start;
    }
  else
    {
      psecondMax=interval*2;
    }
  pfirst=0;
  psecond=interval;
  pout=0;
  n = 0;
  while(1)
    {
      //nobody hit the tail
      if(pfirst!=interval&&psecond!=psecondMax)
	{
	  if(source[start+pfirst]>source[start+psecond])
	    {
	      output[start+pout]=source[start+psecond];
	      psecond++;
	    }
	  else
	    {
	      output[start+pout]=source[start+pfirst];
	      pfirst++;
	    }
	}
      else
	{
	  if(pfirst==interval&&psecond!=psecondMax)
	    {
	      //pfirst hit the tail
	      output[start+pout]=source[start+psecond];
	      psecond++;
	    }
	  else
	    {
	      if (pfirst!=interval&&psecond==psecondMax)
		{
		  //psecond hit the tail
		  output[start+pout]=source[start+pfirst];
		  pfirst++;
	    	}
	    }
	}
      pout++;
      if(pout==psecondMax)
	{
	  return;
	}
    }
  
}
